home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / VELENG10.ZIP / HEURIST.C < prev    next >
C/C++ Source or Header  |  1997-07-27  |  13KB  |  525 lines
  1. // ****************************************************************************
  2. // *                                                                          *
  3. // *                      Velena Source Code V1.0                             *
  4. // *                   Written by Giuliano Bertoletti                         *
  5. // *       Based on the knowledged approach of Louis Victor Allis             *
  6. // *   Copyright (C) 1996-97 by Giuliano Bertoletti & GBE 32241 Software PR   *
  7. // *                                                                          *
  8. // ****************************************************************************
  9.  
  10. // Portable engine version.
  11. // read the README file for further informations.
  12.  
  13. // ==========================================================================
  14.  
  15.  
  16. #include <stdio.h>
  17. #include <string.h>
  18. #include <stdlib.h>
  19. #include <malloc.h>
  20.  
  21. #include "connect4.h"
  22. #include "con4vals.h"
  23. #include "rules.h"
  24. #include "pnsearch.h"
  25. #include "proto.h"
  26.  
  27. #include "heurist.h"
  28.  
  29. extern short nodeseq[];
  30. extern struct board *auxboard;
  31.  
  32. struct bintree *streeroot;
  33. struct node *rootnode;
  34.  
  35. char fight_for_win=0;
  36.  
  37. void fight(char t)
  38.     {
  39.     fight_for_win=t;
  40.     }
  41.  
  42. short whatfight()
  43.     {
  44.     return (short)fight_for_win;
  45.     }
  46.  
  47. long her_node_expanded,her_node_not_expanded;
  48.  
  49. void her_generate_all_children(struct node *node)
  50.     {
  51.     struct node *dummy,*symm;
  52.     short x,y,x1,y1,backtrace;
  53.  
  54.     for(x=0;x<BOARDX;x++)
  55.         {
  56.         if(node->child[x]) fatal_error("Tried to allocate a node twice!");
  57.         else if(node->stack[x]<BOARDY)
  58.             {
  59.             node->child[x]=(struct node *)malloc(sizeof(struct node));
  60.             symm=(struct node *)malloc(sizeof(struct node));
  61.  
  62.             if(!node->child[x] || !symm)
  63.                 fatal_error("Not enough memory to build the tree");
  64.  
  65.             memcpy(node->child[x]->square,node->square,(BOARDX+1)*(BOARDY+2));
  66.             memcpy(node->child[x]->stack,node->stack,BOARDX+1);
  67.             backtrace=x;
  68.  
  69.             node->child[x]->square[ELM(x,node->child[x]->stack[x]++)]=node->turn;
  70.             node->child[x]->turn=node->turn^SWITCHSIDE;
  71.             symm->turn=node->turn^SWITCHSIDE;
  72.  
  73.             for(y1=0;y1<BOARDY;y1++)
  74.                 {
  75.                 symm->square[ELM(BOARDX,y1)]=node->child[x]->square[ELM(BOARDX,y1)];
  76.                 for(x1=0;x1<BOARDX;x1++)
  77.                     symm->square[ELM(x1,y1)]=node->child[x]->square[ELM(BOARDX-x1-1,y1)];
  78.                 }
  79.  
  80.             symm->stack[BOARDX]=node->child[x]->stack[BOARDX];
  81.             for(x1=0;x1<BOARDX;x1++)
  82.                 symm->stack[x1]=node->child[x]->stack[BOARDX-x1-1];
  83.  
  84.             if(bin_compare(symm->square,node->child[x]->square)>0)
  85.                 {
  86.                 dummy=symm;
  87.                 symm=node->child[x];
  88.                 node->child[x]=dummy;
  89.                 backtrace=BOARDX-x-1;
  90.                 }
  91.  
  92.             dummy=fast_check_node(streeroot,node->child[x],0);
  93.             if(dummy)
  94.                 {
  95.                 free(node->child[x]);
  96.                 node->child[x]=dummy;
  97.                 node->child[x]->parent[backtrace]=node;
  98.                 her_node_not_expanded++;
  99.                 }
  100.             else
  101.                 {
  102.                 node->child[x]->expanded=NO;
  103.                 node->child[x]->evaluated=NO;
  104.  
  105.                 for(y=0;y<BOARDX;y++)
  106.                     node->child[x]->parent[y]=NULL;
  107.  
  108.                 node->child[x]->parent[backtrace]=node;
  109.  
  110.                 for(y=0;y<BOARDX;y++)
  111.                     node->child[x]->child[y]=NULL;
  112.  
  113.                 her_node_expanded++;
  114.  
  115.                 if(node->type==AND_TYPE) node->child[x]->type=OR_TYPE;
  116.                 else if(node->type==OR_TYPE) node->child[x]->type=AND_TYPE;
  117.                 else fatal_error("Could not recognize node type!");
  118.  
  119.                 /*add_node(streeroot,node->child[x]);*/
  120.                 }
  121.  
  122.             node->symmetric[x]=backtrace;
  123.             free(symm);
  124.             }
  125.  
  126.         else node->child[x]=NULL;
  127.         }
  128.     }
  129.  
  130. void her_free_whole_tree(struct bintree *tree)
  131.     {
  132.     short x;
  133.  
  134.     if(!tree) return;
  135.     if(tree->lson) her_free_whole_tree(tree->lson);
  136.     if(tree->rson) her_free_whole_tree(tree->rson);
  137.  
  138.     free(tree->node);
  139.     }
  140.  
  141. short her_evaluate(struct node *node)
  142.     {
  143.     short x,bestmove;
  144.  
  145.     node->evaluated=YES;
  146.  
  147.     for(x=0;x<64;x++)
  148.         auxboard->square[x]=(short)node->square[x];
  149.  
  150.     auxboard->turn=node->turn;
  151.     auxboard->filled=0;
  152.  
  153.     for(x=0;x<BOARDX+1;x++)
  154.         {
  155.         auxboard->stack[x]=(short)node->stack[x];
  156.         if(x<BOARDX) auxboard->filled+=auxboard->stack[x];
  157.         }
  158.  
  159.     if(auxboard->filled==MAXMEN)
  160.         {
  161.         if(rootnode->turn==WHITE)
  162.             {
  163.             if(!fight_for_win)
  164.                 {
  165.                 if(rootnode->type==OR_TYPE) node->value=DISPROVED;
  166.                 else node->value=PROVED;
  167.                 }
  168.             else
  169.                 {
  170.                 if(rootnode->type==OR_TYPE) node->value=PROVED;
  171.                 else node->value=DISPROVED;
  172.                 }
  173.             }
  174.         else
  175.             {
  176.             if(!fight_for_win)
  177.                 {
  178.                 if(rootnode->type==OR_TYPE) node->value=PROVED;
  179.                 else node->value=DISPROVED;
  180.                 }
  181.             else
  182.                 {
  183.                 if(rootnode->type==OR_TYPE) node->value=DISPROVED;
  184.                 else node->value=PROVED;
  185.                 }
  186.             }
  187.         return -1;
  188.         }
  189.  
  190.     bestmove=fast_try_to_win(auxboard);
  191.     if(bestmove!=-1)
  192.         {
  193.         if(node->type==OR_TYPE)  node->value=PROVED;
  194.         if(node->type==AND_TYPE) node->value=DISPROVED;
  195.         }
  196.  
  197.     else node->value=UNKNOWN;
  198.  
  199.     return bestmove;
  200.     }
  201.  
  202. short her_resources_available(long maxnodes)
  203.     {
  204.     if(her_node_expanded>maxnodes) return NO;
  205.     return YES;
  206.     }
  207.  
  208. struct node *her_select_most_proving_node(struct node *node,struct info *info)
  209.     {
  210.     short i,flag,depth=0;
  211.  
  212.     while(node->expanded)
  213.         {
  214.         i=0;
  215.         flag=FALSE;
  216.  
  217.         switch(node->type)
  218.             {
  219.             case OR_TYPE:
  220.                 do
  221.                     {
  222.                     if(node->child[nodeseq[i]] &&
  223.                         node->child[nodeseq[i]]->proof==node->proof)
  224.                             flag=TRUE;
  225.                     else i++;
  226.                     } while(i<BOARDX && !flag);
  227.  
  228.                 if(!flag)
  229.                     fatal_error("Could not find a good OR child!");
  230.                 break;
  231.  
  232.             case AND_TYPE:
  233.                 do
  234.                     {
  235.                     if(node->child[nodeseq[i]] &&
  236.                         node->child[nodeseq[i]]->disproof==node->disproof)
  237.                             flag=TRUE;
  238.                     else i++;
  239.                     } while(i<BOARDX && !flag);
  240.  
  241.                 if(!flag)
  242.                     fatal_error("Could not find a good AND child!");
  243.                 break;
  244.  
  245.             default:
  246.                 fatal_error("Unknown node type!");
  247.                 break;
  248.  
  249.             }
  250.         if(!flag) fatal_error("Null node found!");
  251.         else
  252.             {
  253.             if(depth==0) info->bestmove=nodeseq[i];
  254.             node=node->child[nodeseq[i]];
  255.             }
  256.  
  257.         depth++;
  258.         }
  259.  
  260.     info->max_tree_depth=max(info->max_tree_depth,depth+1);
  261.     return node;
  262.     }
  263.  
  264.  
  265. void her_set_pdv_according_to_children(struct node *node)
  266.     {
  267.     short x,children=0;
  268.  
  269.     for(x=0;x<BOARDX;x++)
  270.         if(node->stack[x]<BOARDY) children++;
  271.  
  272.     if(children==0)
  273.         fatal_error("Father without children but of value unknown");
  274.  
  275.     switch(node->type)
  276.         {
  277.         case AND_TYPE:
  278.             node->proof=children;
  279.             node->disproof=1;
  280.             break;
  281.  
  282.         case OR_TYPE:
  283.             node->proof=1;
  284.             node->disproof=children;
  285.             break;
  286.         }
  287.     }
  288.  
  289.  
  290. void her_set_proof_and_disproof_numbers(struct node *node)
  291.     {
  292.     short x;
  293.  
  294.     if(!node) fatal_error("Invalid node choosen");
  295.     else if(node->expanded)
  296.         {
  297.         switch(node->type)
  298.             {
  299.             case AND_TYPE:
  300.                 node->proof=0;
  301.                 node->disproof=MAXVALUE;
  302.                 for(x=0;x<BOARDX;x++)
  303.                     if(node->child[x])
  304.                         {
  305.                         node->proof+=node->child[x]->proof;
  306.                         node->disproof=min(node->disproof,node->child[x]->disproof);
  307.                         }
  308.                     if(node->disproof==0) node->proof=MAXVALUE;
  309.                 break;
  310.  
  311.             case OR_TYPE:
  312.                 node->proof=MAXVALUE;
  313.                 node->disproof=0;
  314.                 for(x=0;x<BOARDX;x++)
  315.                     if(node->child[x])
  316.                         {
  317.                         node->proof=min(node->proof,node->child[x]->proof);
  318.                         node->disproof+=node->child[x]->disproof;
  319.                         }
  320.                     if(node->proof==0) node->disproof=MAXVALUE;
  321.                 break;
  322.  
  323.             default:
  324.                 fatal_error("I don't know what to prove or disprove!");
  325.                 break;
  326.             }
  327.  
  328.         if(node->proof<0 || node->disproof<0)
  329.             fatal_error("Proof and disproof numbers cannot be lower than zero");
  330.  
  331.         }
  332.     else if(node->evaluated)
  333.         {
  334.         switch(node->value)
  335.             {
  336.             case PROVED:
  337.                 node->proof=0;
  338.                 node->disproof=MAXVALUE;
  339.                 break;
  340.  
  341.             case DISPROVED:
  342.                 node->proof=MAXVALUE;
  343.                 node->disproof=0;
  344.                 break;
  345.  
  346.             case UNKNOWN:
  347.                 her_set_pdv_according_to_children(node);
  348.                 break;
  349.             }
  350.         }
  351.     else fatal_error("Asked to set a node never evaluated!");
  352.     }
  353.  
  354. void her_develop_node(struct node *node)
  355.     {
  356.     short i;
  357.  
  358.     node->expanded=YES;
  359.     her_generate_all_children(node);
  360.  
  361.     for(i=0;i<BOARDX;i++)
  362.         {
  363.         if(node->child[i])
  364.             {
  365.             her_evaluate(node->child[i]);
  366.             her_set_proof_and_disproof_numbers(node->child[i]);
  367.             }
  368.         }
  369.     }
  370.  
  371. void her_update_ancestors(struct node *node)
  372.     {
  373.     struct node *previous_node;
  374.     short x;
  375.  
  376.     if(node)
  377.         {
  378.         her_set_proof_and_disproof_numbers(node);
  379.  
  380.         for(x=0;x<BOARDX;x++)
  381.             if(node->parent[x]) her_update_ancestors(node->parent[x]);
  382.         }
  383.     }
  384.  
  385. void her_pn_search(struct node *root,long maxnodes,struct info *info)
  386.     {
  387.     struct node *her_most_proving_node;
  388.     short fl;
  389.  
  390.     info->max_tree_depth=1;
  391.     info->bestmove=her_evaluate(root);
  392.     her_set_proof_and_disproof_numbers(root);
  393.  
  394.     while(root->proof!=0 && root->disproof!=0 && her_resources_available(maxnodes))
  395.         {
  396.         her_most_proving_node=her_select_most_proving_node(root,info);
  397.         her_develop_node(her_most_proving_node);
  398.         her_update_ancestors(her_most_proving_node);
  399.         }
  400.  
  401.     if(root->proof==0) root->value=PROVED;
  402.     else if (root->disproof==0) root->value=DISPROVED;
  403.     else root->value=UNKNOWN;
  404.     }
  405.  
  406. short heuristic_search(struct node *mynode,long maxnodenum)
  407.     {
  408.     struct info info;
  409.     short x;
  410.  
  411.     if(mynode->expanded || mynode->evaluated)
  412.         fatal_error("Request to evaluate a node already evaluated or expanded!");
  413.  
  414.     mynode->evaluated=YES;
  415.  
  416.     rootnode=(struct node *)malloc(sizeof(struct node));
  417.     if(!rootnode) fatal_error("Not enough memory");
  418.  
  419.     memcpy(rootnode,mynode,sizeof(struct node));
  420.  
  421.     her_node_expanded=0L;
  422.     her_node_not_expanded=0L;
  423.  
  424.     for(x=0;x<BOARDX;x++)
  425.         rootnode->parent[x]=NULL;
  426.  
  427.     streeroot=fast_init_bin_tree(rootnode);
  428.     her_pn_search(rootnode,maxnodenum,&info);
  429.  
  430.     mynode->value=rootnode->value;
  431.     mynode->proof=rootnode->proof;
  432.     mynode->disproof=rootnode->disproof;
  433.  
  434.     her_free_whole_tree(streeroot);
  435.     fast_free_bin_tree(streeroot);
  436.  
  437.     if(mynode->value!=UNKNOWN) return YES;
  438.     return NO;
  439.     }
  440.  
  441.  
  442. /* Avoid tricks */
  443.  
  444. short heuristic_play_best(struct board *board,long maxnodenum)
  445.     {
  446.     struct board *tempboard;
  447.     struct info info;
  448.     short mymove,fl;
  449.     struct node *symmetric;
  450.     short x,y,issymm=NO;
  451.  
  452.     auxboard=board;
  453.     tempboard=(struct board *)malloc(sizeof(struct board));
  454.     if(!tempboard) fatal_error("Cannot store temporary board");
  455.     memcpy(tempboard,board,sizeof(struct board));
  456.  
  457.     rootnode=(struct node *)malloc(sizeof(struct node));
  458.     symmetric=(struct node *)malloc(sizeof(struct node));
  459.     if(!rootnode || !symmetric) fatal_error("Not enough memory");
  460.  
  461.     for(y=0;y<BOARDY;y++)
  462.         {
  463.         rootnode->square[ELM(BOARDX,y)]=(unsigned char)(board->square[ELM(BOARDX,y)]&0xff);
  464.         symmetric->square[ELM(BOARDX,y)]=(unsigned char)(board->square[ELM(BOARDX,y)]&0xff);
  465.         for(x=0;x<BOARDX;x++)
  466.             {
  467.             rootnode->square[ELM(x,y)]=(unsigned char)(board->square[ELM(x,y)]&0xff);
  468.             symmetric->square[ELM(x,y)]=(unsigned char)(board->square[ELM(BOARDX-x-1,y)]&0xff);
  469.             }
  470.         }
  471.  
  472.     rootnode->turn=board->turn;
  473.     symmetric->turn=board->turn;
  474.  
  475.     for(x=0;x<BOARDX;x++)
  476.         {
  477.         rootnode->stack[x]=(unsigned char)(board->stack[x]&0xff);
  478.         symmetric->stack[x]=(unsigned char)(board->stack[BOARDX-1-x]&0xff);
  479.         }
  480.  
  481.     rootnode->stack[BOARDX]=(unsigned char)(board->stack[BOARDX]&&0xff);
  482.     symmetric->stack[BOARDX]=(unsigned char)(board->stack[BOARDX]&&0xff);
  483.  
  484.     if(bin_compare(symmetric->square,rootnode->square)>0)
  485.         {
  486.         free(rootnode);
  487.         rootnode=symmetric;
  488.         issymm=YES;
  489.         }
  490.     else free(symmetric);
  491.  
  492.     her_node_expanded=0L;
  493.     her_node_not_expanded=0L;
  494.  
  495.     for(x=0;x<BOARDX;x++)
  496.         {
  497.         rootnode->parent[x]=NULL;
  498.         rootnode->child[x]=NULL;
  499.         }
  500.  
  501.     rootnode->evaluated=NO;
  502.     rootnode->expanded=NO;
  503.     rootnode->value=UNKNOWN;
  504.     rootnode->type=OR_TYPE;
  505.  
  506.     streeroot=fast_init_bin_tree(rootnode);
  507.     her_pn_search(rootnode,maxnodenum,&info);
  508.     mymove=info.bestmove;
  509.  
  510.     if(rootnode->value==UNKNOWN) mymove=-1;
  511.     else if(rootnode->value==DISPROVED) mymove=-2;
  512.     else if(issymm) mymove=BOARDX-1-mymove;
  513.  
  514.     her_free_whole_tree(streeroot);
  515.     fast_free_bin_tree(streeroot);
  516.  
  517.     memcpy(board,tempboard,sizeof(struct board));
  518.     free(tempboard);
  519.  
  520.     board->nodes_visited=her_node_expanded+her_node_not_expanded;
  521.     board->maxtreedepth=info.max_tree_depth;
  522.     return mymove;
  523.     }
  524.  
  525.